home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / BitString.cc < prev    next >
C/C++ Source or Header  |  1994-05-31  |  36KB  |  1,607 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitString class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <BitString.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #include <Obstack.h>
  29. #include <AllocRing.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32. #include <strstream.h>
  33.  
  34. void BitString::error(const char* msg) const
  35. {
  36.   (*lib_error_handler)("BitString", msg);
  37. }
  38.  
  39. //  globals
  40.  
  41. BitStrRep    _nilBitStrRep = {  0, 1, {0} };
  42.  
  43. BitString _nil_BitString;
  44.  
  45. #define MINBitStrRep_SIZE  8
  46. #define MAXBitStrRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  47.  
  48. #ifndef MALLOC_MIN_OVERHEAD
  49. #define MALLOC_MIN_OVERHEAD    4
  50. #endif
  51.  
  52. #define ONES  ((_BS_word)(~0L))
  53. #define MAXBIT  (((_BS_word)1) << (BITSTRBITS - 1))
  54.  
  55. /*
  56.  *  bit manipulation utilities
  57. */
  58.  
  59. // break things up into .s indices and positions
  60.  
  61. inline static int BitStr_len(int l)
  62. {
  63.   return (unsigned)(l) / BITSTRBITS + 1;
  64. }
  65.  
  66.  
  67. // mask out low bits
  68.  
  69. static inline _BS_word lmask(int p)
  70. {
  71.   return ONES _BS_RIGHT p;
  72. }
  73.  
  74. // mask out high bits
  75.  
  76. static inline _BS_word rmask(int p)
  77. {
  78.   int s = BITSTRBITS - 1 - p;
  79.   if (s <= 0)
  80.     return ONES;
  81.   else
  82.     return ONES _BS_LEFT s;
  83. }
  84.  
  85.  
  86. // mask out unused bits in last word of rep
  87.  
  88. inline static void check_last(BitStrRep* r)
  89. {
  90.   int bit_len_mod = r->len & (BITSTRBITS - 1);
  91.   if (bit_len_mod)
  92.     r->s[r->len / BITSTRBITS] &= ONES _BS_LEFT (BITSTRBITS - bit_len_mod);
  93. }
  94.  
  95. // merge bits from next word
  96.  
  97. static inline _BS_word borrow_hi(const _BS_word a[], int ind, 
  98.                                       int maxind, int p)
  99. {
  100.   if (p == 0)
  101.     return a[ind];
  102.   else if (ind < maxind)
  103.     return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
  104.   else
  105.     return (a[ind] _BS_LEFT p);
  106. }
  107.  
  108. // merge bits from prev word
  109.  
  110. static inline _BS_word borrow_lo(const _BS_word a[], int ind, 
  111.                                       int minind, int p)
  112. {
  113.   _BS_word word = a[ind] _BS_RIGHT (BITSTRBITS - 1 - p);
  114.   if (ind > minind)
  115.     word |= (a[ind-1] _BS_LEFT (p + 1));
  116.   return word;
  117. }
  118.  
  119. // same with bounds check (for masks shorter than patterns)
  120.  
  121. static inline _BS_word safe_borrow_hi(const _BS_word a[], int ind, 
  122.                                            int maxind, int p)
  123. {
  124.   if (ind > maxind)
  125.     return 0;
  126.   else if (p == 0)
  127.     return a[ind];
  128.   else if (ind == maxind)
  129.     return a[ind] _BS_LEFT p;
  130.   else
  131.     return (a[ind] _BS_LEFT p) | (a[ind+1] _BS_RIGHT (BITSTRBITS - p));
  132. }
  133.  
  134.  
  135. // allocate a new rep; pad to near a power of two
  136.  
  137. inline static BitStrRep* BSnew(int newlen)
  138. {
  139.   unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(_BS_word) 
  140.     + MALLOC_MIN_OVERHEAD;
  141.   unsigned int allocsiz = MINBitStrRep_SIZE;;
  142.   while (allocsiz < siz) allocsiz <<= 1;
  143.   allocsiz -= MALLOC_MIN_OVERHEAD;
  144.   if (allocsiz >= MAXBitStrRep_SIZE * sizeof(_BS_word))
  145.     (*lib_error_handler)("BitString", "Requested length out of range");
  146.     
  147.   BitStrRep* rep = (BitStrRep *) new char[allocsiz];
  148.   memset(rep, 0, allocsiz);
  149.   rep->sz =
  150.     (allocsiz - sizeof(BitStrRep) + sizeof(_BS_word)) / sizeof(_BS_word);
  151.   return rep;
  152. }
  153.  
  154. inline void
  155. copy_bits (_BS_word* pdst, _BS_size_t dstbit,
  156.        const _BS_word* psrc, _BS_size_t srcbit,
  157.        _BS_size_t length)
  158. {
  159.   _BS_NORMALIZE (pdst, dstbit);
  160.   _BS_NORMALIZE (psrc, srcbit);
  161.   _BS_copy (pdst, dstbit, psrc, srcbit, length);
  162. }
  163.  
  164. BitStrRep* BStr_alloc(BitStrRep* old, const _BS_word* src,
  165.                       int startpos, int endp, int newlen)
  166. {
  167.   if (old == &_nilBitStrRep) old = 0; 
  168.   if (newlen < 0) newlen = 0;
  169.   int news = BitStr_len(newlen);
  170.   BitStrRep* rep;
  171.   if (old == 0 || news > old->sz)
  172.     rep = BSnew(newlen);
  173.   else
  174.     rep = old;
  175.   rep->len = newlen;
  176.  
  177.   if (src != 0 && endp > 0 && (src != rep->s || startpos > 0))
  178.     copy_bits (rep->s, 0, src, startpos, endp - startpos);
  179.  
  180.   check_last(rep);
  181.  
  182.   if (old != rep && old != 0) delete old;
  183.  
  184.   return rep;
  185. }
  186.  
  187. BitStrRep* BStr_resize(BitStrRep* old, int newlen)
  188. {
  189.   BitStrRep* rep;
  190.   if (newlen < 0) newlen = 0;
  191.   int news = BitStr_len(newlen);
  192.   if (old == 0 || old == &_nilBitStrRep)
  193.   {
  194.     rep = BSnew(newlen);
  195.   }
  196.   else if (news > old->sz)
  197.   {
  198.     rep = BSnew(newlen);
  199.     memcpy(rep->s, old->s, BitStr_len(old->len) * sizeof(_BS_word));
  200.     delete old;
  201.   }
  202.   else
  203.     rep = old;
  204.  
  205.   rep->len = newlen;
  206.   check_last(rep);
  207.   return rep;
  208. }
  209.  
  210. BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
  211. {
  212.   BitStrRep* rep;
  213.   if (old == src && old != &_nilBitStrRep) return old; 
  214.   if (old == &_nilBitStrRep) old = 0;
  215.   if (src == &_nilBitStrRep) src = 0;
  216.   if (src == 0)
  217.   {
  218.     if (old == 0)
  219.       rep = BSnew(0);
  220.     else
  221.       rep = old;
  222.     rep->len = 0;
  223.   }
  224.   else 
  225.   {
  226.     int newlen = src->len;
  227.     int news = BitStr_len(newlen);
  228.     if (old == 0 || news  > old->sz)
  229.     {
  230.       rep = BSnew(newlen);
  231.       if (old != 0) delete old;
  232.     }
  233.     else
  234.       rep = old;
  235.     
  236.     memcpy(rep->s, src->s, news * sizeof(_BS_word));
  237.     rep->len = newlen;
  238.   }
  239.   check_last(rep);
  240.   return rep;
  241. }
  242.  
  243.  
  244. int operator == (const BitString& x, const BitString& y)
  245. {
  246.   return x.rep->len == y.rep->len && 
  247.     memcmp((void*)x.rep->s, (void*)y.rep->s, 
  248.          BitStr_len(x.rep->len) * sizeof(_BS_word)) == 0;
  249. }
  250.  
  251. int operator <= (const BitString& x, const BitString& y)
  252. {
  253.   unsigned int  xl = x.rep->len;
  254.   unsigned int  yl = y.rep->len;
  255.   if (xl > yl)
  256.     return 0;
  257.  
  258.   const _BS_word* xs = x.rep->s;
  259.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  260.   const _BS_word* ys = y.rep->s;
  261.  
  262.   while (xs < topx)
  263.   {
  264.     _BS_word a = *xs++;
  265.     _BS_word b = *ys++;
  266.     if ((a | b) != b)
  267.       return 0;
  268.   }
  269.   return 1;
  270. }
  271.  
  272. int operator < (const BitString& x, const BitString& y)
  273. {
  274.   unsigned short xl = x.rep->len;
  275.   unsigned short yl = y.rep->len;
  276.   if (xl > yl)
  277.     return 0;
  278.  
  279.   const _BS_word* xs = x.rep->s;
  280.   const _BS_word* ys = y.rep->s;
  281.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  282.   const _BS_word* topy = &(ys[BitStr_len(yl)]);
  283.   int one_diff = 0;
  284.   while (xs < topx)
  285.   {
  286.     _BS_word a = *xs++;
  287.     _BS_word b = *ys++;
  288.     _BS_word c = a | b;
  289.     if (c != b)
  290.       return 0;
  291.     else if (c != a)
  292.       one_diff = 1;
  293.   }
  294.   if (one_diff)
  295.     return 1;
  296.   else
  297.   {
  298.     while (ys < topy)
  299.       if (*ys++ != 0)
  300.         return 1;
  301.     return 0;
  302.   }
  303. }
  304.  
  305. int lcompare(const BitString& x, const BitString& y)
  306. {
  307.   return _BS_lcompare_0 (x.rep->s, x.rep->len, y.rep->s, y.rep->len);
  308. }
  309.  
  310. int BitString::count(unsigned int b) const
  311. {
  312.   int count = _BS_count (rep->s, 0, rep->len);
  313.   if (!b)
  314.     count = rep->len - count;
  315.   return count;
  316. }
  317.  
  318.  
  319. BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
  320. {
  321.   r = BStr_copy(r, src);
  322.   _BS_word* rs = r->s;
  323.   _BS_word* topr = &(rs[BitStr_len(r->len)]);
  324.   while (rs < topr)
  325.   {
  326.     _BS_word cmp = ~(*rs);
  327.     *rs++ = cmp;
  328.   }
  329.   check_last(r);
  330.   return r;
  331. }
  332.  
  333.  
  334. BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  335. {
  336.   int xrsame = x == r;
  337.   int yrsame = y == r;
  338.  
  339.   unsigned int  xl = x->len;
  340.   unsigned int  yl = y->len;
  341.   unsigned int  rl = (xl <= yl)? xl : yl;
  342.  
  343.   r = BStr_resize(r, rl);
  344.  
  345.   _BS_word* rs = r->s;
  346.   _BS_word* topr = &(rs[BitStr_len(rl)]);
  347.   const _BS_word* xs = (xrsame)? rs : x->s;
  348.   const _BS_word* ys = (yrsame)? rs : y->s;
  349.  
  350.   while (rs < topr) *rs++ = *xs++ & *ys++;
  351.   check_last(r);
  352.   return r;
  353. }
  354.  
  355. BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  356. {
  357.   unsigned int  xl = x->len;
  358.   unsigned int  yl = y->len;
  359.   unsigned int  rl = (xl >= yl)? xl : yl;
  360.   int xrsame = x == r;
  361.   int yrsame = y == r;
  362.  
  363.   r = BStr_resize(r, rl);
  364.  
  365.   _BS_word* rs = r->s;
  366.   const _BS_word* xs = (xrsame)? rs : x->s;
  367.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  368.   const _BS_word* ys = (yrsame)? rs : y->s;
  369.   const _BS_word* topy = &(ys[BitStr_len(yl)]);
  370.  
  371.   if (xl <= yl)
  372.   {
  373.     while (xs < topx) *rs++ = *xs++ | *ys++;
  374.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  375.   }
  376.   else
  377.   {
  378.     while (ys < topy) *rs++ = *xs++ | *ys++;
  379.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  380.   }
  381.   check_last(r);
  382.   return r;
  383. }
  384.  
  385.  
  386. BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  387. {
  388.   unsigned int  xl = x->len;
  389.   unsigned int  yl = y->len;
  390.   unsigned int  rl = (xl >= yl)? xl : yl;
  391.   int xrsame = x == r;
  392.   int yrsame = y == r;
  393.  
  394.   r = BStr_resize(r, rl);
  395.  
  396.   _BS_word* rs = r->s;
  397.   const _BS_word* xs = (xrsame)? rs : x->s;
  398.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  399.   const _BS_word* ys = (yrsame)? rs : y->s;
  400.   const _BS_word* topy = &(ys[BitStr_len(yl)]);
  401.  
  402.   if (xl <= yl)
  403.   {
  404.     while (xs < topx) *rs++ = *xs++ ^ *ys++;
  405.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  406.   }
  407.   else
  408.   {
  409.     while (ys < topy) *rs++ = *xs++ ^ *ys++;
  410.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  411.   }
  412.   check_last(r);
  413.   return r;
  414. }
  415.  
  416.  
  417. BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  418. {
  419.   unsigned int  xl = x->len;
  420.   unsigned int  yl = y->len;
  421.   int xrsame = x == y;
  422.   int yrsame = y == r;
  423.  
  424.   r = BStr_resize(r, xl);
  425.  
  426.   _BS_word* rs = r->s;
  427.   const _BS_word* xs = (xrsame)? rs : x->s;
  428.   const _BS_word* topx = &(xs[BitStr_len(xl)]);
  429.   const _BS_word* ys = (yrsame)? rs : y->s;
  430.   const _BS_word* topy = &(ys[BitStr_len(yl)]);
  431.  
  432.   if (xl <= yl)
  433.   {
  434.     while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  435.   }
  436.   else
  437.   {
  438.     while (ys < topy) *rs++ = *xs++ & ~(*ys++);
  439.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  440.   }
  441.   check_last(r);
  442.   return r;
  443. }
  444.  
  445.  
  446. BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  447. {
  448.   unsigned int  xl = x->len;
  449.   unsigned int  yl = y->len;
  450.   unsigned int  rl = xl + yl;
  451.   int xrsame = x == r;
  452.   int yrsame = y == r;
  453.  
  454.   if (yrsame)
  455.   {
  456.     if (xrsame)
  457.     {
  458.       r = BStr_resize(r, rl);
  459.       copy_bits (r->s, xl, r->s, 0, yl);
  460.     }
  461.     else
  462.     {
  463.       BitStrRep* tmp = BStr_copy(0, y);
  464.       r = BStr_resize(r, rl);
  465.       _BS_copy_0(r->s, x->s, xl);
  466.       copy_bits (r->s, xl, tmp->s, 0, yl);
  467.       delete tmp;
  468.     }
  469.   }
  470.   else
  471.   {
  472.     r = BStr_resize(r, rl);
  473.     if (!xrsame) _BS_copy_0(r->s, x->s, xl);
  474.     copy_bits (r->s, xl, y->s, 0, yl);
  475.   }
  476.   check_last(r);
  477.   return r;
  478. }
  479.  
  480. BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r)
  481. {
  482.   unsigned int  xl = x->len;
  483.   int xrsame = x == r;
  484.   r = BStr_resize(r, xl+1);
  485.   if (!xrsame)
  486.     _BS_copy_0(r->s, x->s, xl);
  487.   if (bit)
  488.     r->s[BitStr_index(xl)] |= _BS_BITMASK(BitStr_pos(xl));
  489.   else
  490.     r->s[BitStr_index(xl)] &= ~(_BS_BITMASK(BitStr_pos(xl)));
  491.   check_last(r);
  492.   return r;
  493. }
  494.  
  495. BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r)
  496. {
  497.   int xrsame = x == r;
  498.   int  xl = x->len;
  499.   int  rl = xl + s;
  500.   if (s == 0)
  501.     r = BStr_copy(r, x);
  502.   else if (rl <= 0)
  503.   {
  504.     r = BStr_resize(r, 0);
  505.     r->len = 0;
  506.     r->s[0] = 0;
  507.   }
  508.   else if (s > 0)
  509.   {
  510.     r = BStr_resize(r, rl);
  511.     const _BS_word* xs = (xrsame)? r->s : x->s;
  512.     copy_bits (r->s, s, xs, 0, xl);
  513.     _BS_clear (r->s, 0, s);
  514.   }
  515.   else if (xrsame)
  516.   {
  517.     r = BStr_resize(r, xl);
  518.     r->len = rl;
  519.     copy_bits (r->s, 0, r->s, -s, xl + s);
  520.   }
  521.   else
  522.   {
  523.     r = BStr_resize(r, rl);
  524.     copy_bits (r->s, 0, x->s, -s, xl + s);
  525.   }
  526.   check_last(r);
  527.   return r;
  528. }
  529.  
  530.  
  531. void BitString::set(int p)
  532. {
  533.   if (p < 0) error("Illegal bit index");
  534.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  535.   rep->s[BitStr_index(p)] |= _BS_BITMASK(BitStr_pos(p));
  536. }
  537.  
  538. void BitString::assign(int p, unsigned int bit)
  539. {
  540.   if (p < 0) error("Illegal bit index");
  541.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  542.   if (bit)
  543.     rep->s[BitStr_index(p)] |= _BS_BITMASK(BitStr_pos(p));
  544.   else
  545.       rep->s[BitStr_index(p)] &= ~(_BS_BITMASK(BitStr_pos(p)));
  546. }
  547.  
  548. void BitString::clear(int p)
  549. {
  550.   if (p < 0) error("Illegal bit index");
  551.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  552.   rep->s[BitStr_index(p)] &= ~(_BS_BITMASK(BitStr_pos(p)));
  553. }
  554.  
  555. void BitString::clear()
  556. {
  557.   if (rep == &_nilBitStrRep) return;
  558.   _BS_clear (rep->s, 0, rep->len);
  559. }
  560.  
  561. void BitString::set()
  562. {
  563.   if (rep == &_nilBitStrRep) return;
  564.   _BS_word* s = rep->s;
  565.   _BS_word* tops = &(s[BitStr_len(rep->len)]);
  566.   while (s < tops) *s++ = ONES;
  567.   check_last(rep);
  568. }
  569.  
  570. void BitString::invert(int p)
  571. {
  572.   if (p < 0) error("Illegal bit index");
  573.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  574.   rep->s[BitStr_index(p)] ^= _BS_BITMASK(BitStr_pos(p));
  575. }
  576.  
  577. void BitString::set(int from, int to)
  578. {
  579.   if (from < 0 || from > to) error("Illegal bit index");
  580.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  581.  
  582.   _BS_size_t len = to - from + 1;
  583.   _BS_word* xs = rep->s;
  584.   _BS_NORMALIZE (xs, from);
  585.   _BS_invert (xs, from, len);
  586. }
  587.  
  588. void BitString::clear(int from, int to)
  589. {
  590.   if (from < 0 || from > to) error("Illegal bit index");
  591.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  592.  
  593.   _BS_size_t len = to - from + 1;
  594.   _BS_word* xs = rep->s;
  595.   _BS_NORMALIZE (xs, from);
  596.   _BS_clear (xs, from, len);
  597. }
  598.  
  599. void BitString::invert(int from, int to)
  600. {
  601.   if (from < 0 || from > to) error("Illegal bit index");
  602.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  603.   _BS_size_t len = to - from + 1;
  604.   _BS_word* xs = rep->s;
  605.   _BS_NORMALIZE (xs, from);
  606.   _BS_invert (xs, from, len);
  607. }
  608.  
  609.  
  610. int BitString::test(int from, int to) const
  611. {
  612.   if (from < 0 || from > to || (unsigned)(from) >= rep->len) return 0;
  613.   
  614.   _BS_size_t len = to - from + 1;
  615.   _BS_word* xs = rep->s;
  616.   _BS_NORMALIZE (xs, from);
  617.   return _BS_any (xs, from, len);
  618. }
  619.  
  620. int BitString::next(int p, unsigned int b) const
  621. {
  622.   if ((unsigned)(++p) >= rep->len)
  623.     return -1;
  624.  
  625.   int ind = BitStr_index(p);
  626.   int pos = BitStr_pos(p);
  627.   int l = BitStr_len(rep->len);
  628.  
  629.   int j = ind;
  630.   const _BS_word* s = rep->s;
  631.   _BS_word a = s[j] >> pos;
  632.   int i = pos;
  633.  
  634.   if (b != 0)
  635.   {
  636.     for (; i < BITSTRBITS && a != 0; ++i)
  637.     {
  638.       if (a & 1)
  639.         return j * BITSTRBITS + i;
  640.       a >>= 1;
  641.     }
  642.     for (++j; j < l; ++j)
  643.     {
  644.       a = s[j];
  645.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  646.       {
  647.         if (a & 1)
  648.           return j * BITSTRBITS + i;
  649.         a >>= 1;
  650.       }
  651.     }
  652.     return -1;
  653.   }
  654.   else
  655.   {
  656.     int last = BitStr_pos(rep->len);
  657.     if (j == l - 1)
  658.     {
  659.       for (; i < last; ++i)
  660.       {
  661.         if ((a & 1) == 0)
  662.           return j * BITSTRBITS + i;
  663.         a >>= 1;
  664.       }
  665.       return -1;
  666.     }
  667.  
  668.     for (; i < BITSTRBITS; ++i)
  669.     {
  670.       if ((a & 1) == 0)
  671.         return j * BITSTRBITS + i;
  672.       a >>= 1;
  673.     }
  674.     for (++j; j < l - 1; ++j)
  675.     {
  676.       a = s[j];
  677.       if (a != ONES)
  678.       {
  679.         for (i = 0; i < BITSTRBITS; ++i)
  680.         {
  681.           if ((a & 1) == 0)
  682.             return j * BITSTRBITS + i;
  683.           a >>= 1;
  684.         }
  685.       }
  686.     }
  687.     a = s[j];
  688.     for (i = 0; i < last; ++i)
  689.     {
  690.       if ((a & 1) == 0)
  691.         return j * BITSTRBITS + i;
  692.       a >>= 1;
  693.     }
  694.     return -1;
  695.   }
  696. }
  697.  
  698. int BitString::prev(int p, unsigned int b) const
  699. {
  700.   if (--p < 0)
  701.     return -1;
  702.  
  703.   int ind = BitStr_index(p);
  704.   int pos = BitStr_pos(p);
  705.  
  706.   const _BS_word* s = rep->s;
  707.  
  708.   if ((unsigned)(p) >= rep->len)
  709.   {
  710.     ind = BitStr_index(rep->len - 1);
  711.     pos = BitStr_pos(rep->len - 1);
  712.   }
  713.  
  714.   int j = ind;
  715.   _BS_word a = s[j];
  716.  
  717.   int i = pos;
  718.   _BS_word maxbit = ((_BS_word)1) << pos;
  719.  
  720.   if (b != 0)
  721.   {
  722.     for (; i >= 0 && a != 0; --i)
  723.     {
  724.       if (a & maxbit)
  725.         return j * BITSTRBITS + i;
  726.       a <<= 1;
  727.     }
  728.     maxbit = ((_BS_word)1) << (BITSTRBITS - 1);
  729.     for (--j; j >= 0; --j)
  730.     {
  731.       a = s[j];
  732.       for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
  733.       {
  734.         if (a & maxbit)
  735.           return j * BITSTRBITS + i;
  736.         a <<= 1;
  737.       }
  738.     }
  739.     return -1;
  740.   }
  741.   else
  742.   {
  743.     if (a != ONES)
  744.     {
  745.       for (; i >= 0; --i)
  746.       {
  747.         if ((a & maxbit) == 0)
  748.           return j * BITSTRBITS + i;
  749.         a <<= 1;
  750.       }
  751.     }
  752.     maxbit = ((_BS_word)1) << (BITSTRBITS - 1);
  753.     for (--j; j >= 0; --j)
  754.     {
  755.       a = s[j];
  756.       if (a != ONES)
  757.       {
  758.         for (i = BITSTRBITS - 1; i >= 0; --i)
  759.         {
  760.           if ((a & maxbit) == 0)
  761.             return j * BITSTRBITS + i;
  762.           a <<= 1;
  763.         }
  764.       }
  765.     }
  766.     return -1;
  767.   }
  768. }
  769.  
  770.  
  771. int BitString::search(int startx, int lengthx, 
  772.                       const _BS_word* ys, int starty, int lengthy) const
  773. {
  774.   const _BS_word* xs = rep->s;
  775.   int ylen = lengthy - starty;
  776.   int righty = lengthy - 1;
  777.   int rev = startx < 0;
  778.   if (rev)
  779.   {
  780.     int leftx = 0;
  781.     int rightx = lengthx + startx;
  782.     startx = rightx - ylen + 1;
  783.     if (ylen == 0) return startx;
  784.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  785.     
  786.     int xind = BitStr_index(startx);
  787.     int xpos = BitStr_pos(startx);
  788.     int yind = BitStr_index(starty);
  789.     int ypos = BitStr_pos(starty);
  790.     
  791.     int rightxind = BitStr_index(rightx);
  792.  
  793.     _BS_word x = borrow_hi(xs, xind, rightxind, xpos);
  794.   
  795.     int rightyind = BitStr_index(righty);
  796.     int rightypos = BitStr_pos(righty);
  797.     _BS_word y = borrow_hi(ys, yind, rightyind, ypos);
  798.     _BS_word ymask;
  799.     if (yind == rightyind)
  800.       ymask = rmask(rightypos);
  801.     else if (yind+1 == rightyind)
  802.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  803.     else
  804.       ymask = ONES;
  805.     
  806.     int p = startx;
  807.     for (;;)
  808.     {
  809.       if ((x & ymask) == y)
  810.       {
  811.         int xi = xind;
  812.         int yi = yind;
  813.         for (;;)
  814.         {
  815.           if (++yi > rightyind || ++xi > rightxind)
  816.             return p;
  817.           _BS_word tx = borrow_hi(xs, xi, rightxind, xpos);
  818.           _BS_word ty = borrow_hi(ys, yi, rightyind, ypos);
  819.           if (yi == rightyind)
  820.             tx &= rmask(rightypos);
  821.           else if (yi+1 == rightyind)
  822.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  823.           if (tx != ty)
  824.             break;
  825.         }
  826.       }
  827.       if (--p < leftx)
  828.         return -1;
  829.       if (--xpos < 0)
  830.       {
  831.         xpos = BITSTRBITS - 1;
  832.         --xind;
  833.       }
  834.       x = borrow_hi(xs, xind, rightxind, xpos);
  835.     }
  836.   }
  837.   else
  838.   {
  839.  
  840.     int rightx = lengthx - 1;
  841.     if (ylen == 0) return startx;
  842.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  843.     
  844.     int xind = BitStr_index(startx);
  845.     int xpos = BitStr_pos(startx);
  846.     int yind = BitStr_index(starty);
  847.     int ypos = BitStr_pos(starty);
  848.  
  849.     int rightxind = BitStr_index(rightx);
  850.  
  851.     _BS_word x = borrow_hi(xs, xind, rightxind, xpos);
  852.     _BS_word nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  853.   
  854.     int rightyind = BitStr_index(righty);
  855.     int rightypos = BitStr_pos(righty);
  856.     _BS_word y = borrow_hi(ys, yind, rightyind, ypos);
  857.     _BS_word ymask;
  858.     if (yind == rightyind)
  859.       ymask = rmask(rightypos);
  860.     else if (yind+1 == rightyind)
  861.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  862.     else
  863.       ymask = ONES;
  864.   
  865.     int p = startx;
  866.     for (;;)
  867.     {
  868.       if ((x & ymask) == y)
  869.       {
  870.         int xi = xind;
  871.         int yi = yind;
  872.         for (;;)
  873.         {
  874.           if (++yi > rightyind || ++xi > rightxind)
  875.             return p;
  876.           _BS_word tx = borrow_hi(xs, xi, rightxind, xpos);
  877.           _BS_word ty = borrow_hi(ys, yi, rightyind, ypos);
  878.           if (yi == rightyind)
  879.             tx &= rmask(rightypos);
  880.           else if (yi+1 == rightyind)
  881.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  882.           if (tx != ty)
  883.             break;
  884.         }
  885.       }
  886.       if (++p > rightx)
  887.         return -1;
  888.       if (++xpos == BITSTRBITS)
  889.       {
  890.         xpos = 0;
  891.         x = xs[++xind];
  892.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  893.       }
  894.       else
  895.       {
  896.         x >>= 1;
  897.         if (nextx & 1)
  898.           x |= MAXBIT;
  899.         nextx >>= 1;
  900.       }
  901.     }
  902.   }
  903. }
  904.  
  905.  
  906. int BitPattern::search(const _BS_word* xs, int startx, int lengthx) const
  907. {
  908.   const _BS_word* ys = pattern.rep->s;
  909.   const _BS_word* ms = mask.rep->s;
  910.   int righty = pattern.rep->len - 1;
  911.   int rightm = mask.rep->len - 1;
  912.  
  913.   int rev = startx < 0;
  914.   if (rev)
  915.   {
  916.     int leftx = 0;
  917.     int rightx = lengthx + startx;
  918.     startx = rightx - righty;
  919.  
  920.     if (righty < 0) return startx;
  921.     if (startx < 0 || startx >= lengthx) return -1;
  922.   
  923.     int xind = BitStr_index(startx);
  924.     int xpos = BitStr_pos(startx);
  925.     
  926.     int rightxind = BitStr_index(rightx);
  927.  
  928.     int rightmind = BitStr_index(rightm);
  929.     int rightyind = BitStr_index(righty);
  930.     
  931.     _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos);
  932.     _BS_word m = safe_borrow_hi(ms, 0, rightmind, 0);
  933.     _BS_word y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  934.     
  935.     int p = startx;
  936.     for (;;)
  937.     {
  938.       if ((x & m) == y)
  939.       {
  940.         int xi = xind;
  941.         int yi = 0;
  942.         for (;;)
  943.         {
  944.           if (++yi > rightyind || ++xi > rightxind)
  945.             return p;
  946.           _BS_word tm = safe_borrow_hi(ms, yi, rightmind, 0);
  947.           _BS_word ty = safe_borrow_hi(ys, yi, rightyind, 0);
  948.           _BS_word tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  949.           if ((tx & tm) != (ty & tm))
  950.             break;
  951.         }
  952.       }
  953.       if (--p < leftx)
  954.         return -1;
  955.       if (--xpos < 0)
  956.       {
  957.         xpos = BITSTRBITS - 1;
  958.         --xind;
  959.       }
  960.       x = safe_borrow_hi(xs, xind, rightxind, xpos);
  961.     }
  962.   }
  963.   else
  964.   {
  965.  
  966.     int rightx = lengthx - 1;
  967.  
  968.     if (righty < 0) return startx;
  969.     if (startx < 0 || startx >= lengthx) return -1;
  970.     
  971.     int xind = BitStr_index(startx);
  972.     int xpos = BitStr_pos(startx);
  973.     
  974.     int rightxind = BitStr_index(rightx);
  975.  
  976.     int rightmind = BitStr_index(rightm);
  977.     int rightyind = BitStr_index(righty);
  978.     
  979.     _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos);
  980.     _BS_word m = safe_borrow_hi(ms, 0, rightmind, 0);
  981.     _BS_word y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  982.  
  983.     _BS_word nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  984.     
  985.     int p = startx;
  986.     for (;;)
  987.     {
  988.       if ((x & m) == y)
  989.       {
  990.         int xi = xind;
  991.         int yi = 0;
  992.         for (;;)
  993.         {
  994.           if (++yi > rightyind || ++xi > rightxind)
  995.             return p;
  996.           _BS_word tm = safe_borrow_hi(ms, yi, rightmind, 0);
  997.           _BS_word ty = safe_borrow_hi(ys, yi, rightyind, 0);
  998.           _BS_word tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  999.           if ((tx & tm) != (ty & tm))
  1000.             break;
  1001.         }
  1002.       }
  1003.       if (++p > rightx)
  1004.         return -1;
  1005.       if (++xpos == BITSTRBITS)
  1006.       {
  1007.         xpos = 0;
  1008.         x = xs[++xind];
  1009.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1010.       }
  1011.       else
  1012.       {
  1013.         x >>= 1;
  1014.         if (nextx & 1)
  1015.           x |= MAXBIT;
  1016.         nextx >>= 1;
  1017.       }
  1018.     }
  1019.   }
  1020. }
  1021.  
  1022. int BitString::match(int startx, int lengthx, int exact, 
  1023.                      const _BS_word* ys, int starty, int yl) const
  1024. {
  1025.   const _BS_word* xs = rep->s;
  1026.   int ylen = yl - starty;
  1027.   int righty = yl - 1;
  1028.  
  1029.   int rightx;
  1030.   int rev = startx < 0;
  1031.   if (rev)
  1032.   {
  1033.     rightx = lengthx + startx;
  1034.     startx = rightx - ylen + 1;
  1035.     if (exact && startx != 0)
  1036.       return 0;
  1037.   }
  1038.   else
  1039.   {
  1040.     rightx = lengthx - 1;
  1041.     if (exact && rightx - startx != righty)
  1042.       return 0;
  1043.   }
  1044.  
  1045.   if (ylen == 0) return 1;
  1046.   if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
  1047.   
  1048.   int xi   = BitStr_index(startx);
  1049.   int xpos = BitStr_pos(startx);
  1050.   int yi   = BitStr_index(starty);
  1051.   int ypos = BitStr_pos(starty);
  1052.  
  1053.   int rightxind = BitStr_index(rightx);
  1054.   int rightyind = BitStr_index(righty);
  1055.   int rightypos = BitStr_pos(righty);
  1056.  
  1057.   for (;;)
  1058.   {
  1059.     _BS_word x = borrow_hi(xs, xi, rightxind, xpos);
  1060.     _BS_word y = borrow_hi(ys, yi, rightyind, ypos);
  1061.     if (yi == rightyind)
  1062.       x &= rmask(rightypos);
  1063.     else if (yi+1 == rightyind)
  1064.       x &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1065.     if (x != y)
  1066.       return 0;
  1067.     else if (++yi > rightyind || ++xi > rightxind)
  1068.       return 1;
  1069.   }
  1070. }
  1071.  
  1072. int BitPattern::match(const _BS_word* xs, int startx, 
  1073.                       int lengthx, int exact) const
  1074. {
  1075.   const _BS_word* ys = pattern.rep->s;
  1076.   int righty = pattern.rep->len - 1;
  1077.   _BS_word* ms = mask.rep->s;
  1078.   int rightm = mask.rep->len - 1;
  1079.  
  1080.   int rightx;
  1081.   int rev = startx < 0;
  1082.   if (rev)
  1083.   {
  1084.     rightx = lengthx + startx;
  1085.     startx = rightx - righty;
  1086.     if (exact && startx != 0)
  1087.       return 0;
  1088.   }
  1089.   else
  1090.   {
  1091.     rightx = lengthx - 1;
  1092.     if (exact && rightx - startx != righty)
  1093.       return 0;
  1094.   }
  1095.  
  1096.   if (righty < 0) return 1;
  1097.   if (startx < 0 || startx >= lengthx) return 0;
  1098.   
  1099.   int xind = BitStr_index(startx);
  1100.   int xpos = BitStr_pos(startx);
  1101.   int yind = 0;
  1102.  
  1103.   int rightxind = BitStr_index(rightx);
  1104.   int rightyind = BitStr_index(righty);
  1105.   int rightmind = BitStr_index(rightm);
  1106.  
  1107.   for(;;)
  1108.   {
  1109.     _BS_word m = safe_borrow_hi(ms, yind, rightmind, 0);
  1110.     _BS_word x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
  1111.     _BS_word y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
  1112.     if (x != y)
  1113.       return 0;
  1114.     else if (++yind > rightyind || ++xind > rightxind)
  1115.       return 1;
  1116.   }
  1117. }
  1118.  
  1119. BitSubString& BitSubString::operator = (const BitString& y)
  1120. {
  1121.   if (&S == &_nil_BitString)
  1122.     return *this;
  1123.   BitStrRep* targ = S.rep;
  1124.  
  1125.   unsigned int ylen = y.rep->len;
  1126.   int sl = targ->len - len + ylen;
  1127.  
  1128.   if (y.rep == targ || ylen > len)
  1129.   {
  1130.     BitStrRep* oldtarg = targ;
  1131.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1132.     _BS_copy (targ->s, 0, oldtarg->s, 0, pos);
  1133.     copy_bits (targ->s, pos, y.rep->s, 0, ylen);
  1134.     copy_bits (targ->s, pos + ylen, oldtarg->s, pos+len, oldtarg->len-pos-len);
  1135.     delete oldtarg;
  1136.   }
  1137.   else if (len == ylen)
  1138.     copy_bits (targ->s, pos, y.rep->s, 0, len);
  1139.   else if (ylen < len)
  1140.   {
  1141.     copy_bits (targ->s, pos, y.rep->s, 0, ylen);
  1142.     copy_bits (targ->s, pos + ylen, targ->s, pos + len, targ->len - pos - len);
  1143.     targ->len = sl;
  1144.   }
  1145.   check_last(targ);
  1146.   S.rep = targ;
  1147.   return *this;
  1148. }
  1149.  
  1150. BitSubString& BitSubString::operator = (const BitSubString& y)
  1151. {
  1152.   if (&S == &_nil_BitString)
  1153.     return *this;
  1154.   BitStrRep* targ = S.rep;
  1155.   
  1156.   if (len == 0 || pos >= targ->len)
  1157.     return *this;
  1158.   
  1159.   int sl = targ->len - len + y.len;
  1160.   
  1161.   if (y.S.rep == targ || y.len > len)
  1162.   {
  1163.     BitStrRep* oldtarg = targ;
  1164.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1165.     _BS_copy_0(targ->s, oldtarg->s, pos);
  1166.     copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
  1167.     copy_bits (targ->s, pos + y.len, oldtarg->s, pos+len,
  1168.            oldtarg->len-pos-len);
  1169.     delete oldtarg;
  1170.   }
  1171.   else if (len == y.len)
  1172.     copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
  1173.   else if (y.len < len)
  1174.   {
  1175.     copy_bits (targ->s, pos, y.S.rep->s, y.pos, y.len);
  1176.     copy_bits (targ->s, pos + y.len, targ->s, pos + len,
  1177.            targ->len - pos - len);
  1178.     targ->len = sl;
  1179.   }
  1180.   check_last(targ);
  1181.   S.rep = targ;
  1182.   return *this;
  1183. }
  1184.  
  1185. BitSubString BitString::at(int first, int len)
  1186. {
  1187.   return _substr(first, len);
  1188. }
  1189.  
  1190. BitSubString BitString::before(int pos)
  1191. {
  1192.   return _substr(0, pos);
  1193. }
  1194.  
  1195. BitSubString BitString::after(int pos)
  1196. {
  1197.   return _substr(pos + 1, rep->len - (pos + 1));
  1198. }
  1199.  
  1200. BitSubString BitString::at(const BitString& y, int startpos)
  1201. {
  1202.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1203.   return _substr(first,  y.rep->len);
  1204. }
  1205.  
  1206. BitSubString BitString::before(const BitString& y, int startpos)
  1207. {
  1208.   int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1209.   return _substr(0, last);
  1210. }
  1211.  
  1212. BitSubString BitString::after(const BitString& y, int startpos)
  1213. {
  1214.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1215.   if (first >= 0) first += y.rep->len;
  1216.   return _substr(first, rep->len - first);
  1217. }
  1218.  
  1219.  
  1220. BitSubString BitString::at(const BitSubString& y, int startpos)
  1221. {
  1222.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1223.   return _substr(first, y.len);
  1224. }
  1225.  
  1226. BitSubString BitString::before(const BitSubString& y, int startpos)
  1227. {
  1228.   int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1229.   return _substr(0, last);
  1230. }
  1231.  
  1232. BitSubString BitString::after(const BitSubString& y, int startpos)
  1233. {
  1234.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1235.   if (first >= 0) first += y.len;
  1236.   return _substr(first, rep->len - first);
  1237. }
  1238.  
  1239. BitSubString BitString::at(const BitPattern& r, int startpos)
  1240. {
  1241.   int first = r.search(rep->s, startpos, rep->len);
  1242.   return _substr(first, r.pattern.rep->len);
  1243. }
  1244.  
  1245.  
  1246. BitSubString BitString::before(const BitPattern& r, int startpos)
  1247. {
  1248.   int first = r.search(rep->s, startpos, rep->len);
  1249.   return _substr(0, first);
  1250. }
  1251.  
  1252. BitSubString BitString::after(const BitPattern& r, int startpos)
  1253. {
  1254.   int first = r.search(rep->s, startpos, rep->len);
  1255.   if (first >= 0) first += r.pattern.rep->len;
  1256.   return _substr(first, rep->len - first);
  1257. }
  1258.  
  1259. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  1260. #define RETURN(r) return
  1261. #define RETURNS(r) return r;
  1262. #define RETURN_OBJECT(TYPE, NAME) /* nothing */
  1263. #define USE_UNSIGNED 1 /* probably correct */
  1264. #else /* _G_NO_NRV */
  1265. #define RETURN(r) return r
  1266. #define RETURNS(r) /* nothing */
  1267. #define RETURN_OBJECT(TYPE, NAME) TYPE NAME;
  1268. #define USE_UNSIGNED 0 /* probably old bug */
  1269. #endif
  1270.  
  1271. BitString
  1272. common_prefix (const BitString& x, const BitString& y, int startpos)
  1273.      RETURNS(r)
  1274. {
  1275.   RETURN_OBJECT(BitString, r);
  1276.   unsigned int  xl = x.rep->len;
  1277.   unsigned int  yl = y.rep->len;
  1278.  
  1279.   unsigned int startx, starty;
  1280.   if (startpos < 0)
  1281.   {
  1282.     startx = xl + startpos;
  1283.     starty = yl + startpos;
  1284.   }
  1285.   else
  1286.     startx = starty = startpos;
  1287.  
  1288.   if (startx >= xl || starty >= yl)
  1289.     RETURN(r);
  1290.  
  1291.   const _BS_word* xs = &(x.rep->s[BitStr_index(startx)]);
  1292.   _BS_word a = *xs++;
  1293.   unsigned int xp = startx;
  1294.  
  1295.   const _BS_word* ys = &(y.rep->s[BitStr_index(starty)]);
  1296.   _BS_word b = *ys++;
  1297.   unsigned int yp = starty;
  1298.  
  1299.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1300.   {
  1301.     _BS_word xbit = ((_BS_word)1) << (BitStr_pos(xp));
  1302.     _BS_word ybit = ((_BS_word)1) << (BitStr_pos(yp));
  1303.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1304.       break;
  1305.     if (xbit == MAXBIT)
  1306.       a = *xs++;
  1307.     if (ybit == MAXBIT)
  1308.       b = *ys++;
  1309.   }
  1310.   r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  1311.   RETURN(r);
  1312. }
  1313.  
  1314.  
  1315. BitString
  1316. common_suffix (const BitString& x, const BitString& y, int startpos)
  1317.      RETURNS(r)
  1318. {
  1319.   RETURN_OBJECT(BitString, r);
  1320.   unsigned int  xl = x.rep->len;
  1321.   unsigned int  yl = y.rep->len;
  1322.  
  1323.   unsigned int startx, starty;
  1324.   if (startpos < 0)
  1325.   {
  1326.     startx = xl + startpos;
  1327.     starty = yl + startpos;
  1328.   }
  1329.   else
  1330.     startx = starty = startpos;
  1331.  
  1332.   if (startx >= xl || starty >= yl)
  1333.     RETURN(r);
  1334.  
  1335.   const _BS_word* xs = &(x.rep->s[BitStr_index(startx)]);
  1336.   _BS_word a = *xs--;
  1337.   int xp = startx;
  1338.  
  1339.   const _BS_word* ys = &(y.rep->s[BitStr_index(starty)]);
  1340.   _BS_word b = *ys--;
  1341.   int yp = starty;
  1342.  
  1343.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1344.   {
  1345.     _BS_word xbit = ((_BS_word)1) << (BitStr_pos(xp));
  1346.     _BS_word ybit = ((_BS_word)1) << (BitStr_pos(yp));
  1347.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1348.       break;
  1349.     if (xbit == 1)
  1350.       a = *xs--;
  1351.     if (ybit == 1)
  1352.       b = *ys--;
  1353.   }
  1354.   r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  1355.   RETURN(r);
  1356. }
  1357.  
  1358. BitString reverse (const BitString& x)
  1359.      RETURNS(r)
  1360. {
  1361.   RETURN_OBJECT(BitString, r);
  1362.   unsigned int  yl = x.rep->len;
  1363.   BitStrRep* y = BStr_resize(0, yl);
  1364.   if (yl > 0)
  1365.   {
  1366.     const _BS_word* ls = x.rep->s;
  1367.     _BS_word lm = 1;
  1368.     _BS_word* rs = &(y->s[BitStr_index(yl - 1)]);
  1369.     _BS_word rm = ((_BS_word)1) << (BitStr_pos(yl - 1));
  1370.     for (unsigned int  l = 0; l < yl; ++l)
  1371.     {
  1372.       if (*ls & lm)
  1373.         *rs |= rm;
  1374.       if (lm == MAXBIT)
  1375.       {
  1376.         ++ls;
  1377.         lm = 1;
  1378.       }
  1379.       else
  1380.         lm <<= 1;
  1381.       if (rm == 1)
  1382.       {
  1383.         --rs;
  1384.         rm = MAXBIT;
  1385.       }
  1386.       else
  1387.         rm >>= 1;
  1388.     }
  1389.   }
  1390.   r.rep = y;
  1391.   RETURN(r);
  1392. }
  1393.  
  1394. BitString
  1395. atoBitString (const char* s, char f, char t)
  1396.      RETURNS(res)
  1397. {
  1398.   RETURN_OBJECT(BitString, res);
  1399.   int sl = strlen(s);
  1400.   BitStrRep* r = BStr_resize(0, sl);
  1401.   if (sl != 0)
  1402.   {
  1403.     unsigned int  rl = 0;
  1404.     _BS_word* rs = r->s;
  1405.     _BS_word a = 0;
  1406.     _BS_word m = 1;
  1407.     unsigned int  i = 0;
  1408.     for(;;)
  1409.     {
  1410.       char ch = s[i];
  1411.       if (ch != t && ch != f)
  1412.       {
  1413.         *rs = a;
  1414.         break;
  1415.       }
  1416.       ++rl;
  1417.       if (ch == t)
  1418.         a |= m;
  1419.       if (++i == sl)
  1420.       {
  1421.         *rs = a;
  1422.         break;
  1423.       }
  1424.       else if (i % BITSTRBITS == 0)
  1425.       {
  1426.         *rs++ = a;
  1427.         a = 0;
  1428.         m = 1;
  1429.       }
  1430.       else
  1431.         m <<= 1;
  1432.     }
  1433.     r = BStr_resize(r, rl);
  1434.   }
  1435.   res.rep = r;
  1436.   RETURN(res);
  1437. }
  1438.  
  1439. BitPattern
  1440. atoBitPattern (const char* s, char f,char t,char x)
  1441.      RETURNS(r)
  1442. {
  1443.   RETURN_OBJECT(BitPattern, r);
  1444.   int sl = strlen(s);
  1445.   if (sl != 0)
  1446.   {
  1447.     unsigned int  rl = 0;
  1448.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1449.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1450.     _BS_word* rs = r.pattern.rep->s;
  1451.     _BS_word* ms = r.mask.rep->s;
  1452.     _BS_word a = 0;
  1453.     _BS_word b = 0;
  1454.     _BS_word m = 1;
  1455.     unsigned int  i = 0;
  1456.     for(;;)
  1457.     {
  1458.       char ch = s[i];
  1459.       if (ch != t && ch != f && ch != x)
  1460.       {
  1461.         *rs = a;
  1462.         *ms = b;
  1463.         break;
  1464.       }
  1465.       ++rl;
  1466.       if (ch == t)
  1467.       {
  1468.         a |= m;
  1469.         b |= m;
  1470.       }
  1471.       else if (ch == f)
  1472.       {
  1473.         b |= m;
  1474.       }
  1475.       if (++i == sl)
  1476.       {
  1477.         *rs = a;
  1478.         *ms = b;
  1479.         break;
  1480.       }
  1481.       else if (i % BITSTRBITS == 0)
  1482.       {
  1483.         *rs++ = a;
  1484.         *ms++ = b;
  1485.         a = 0;
  1486.         b = 0;
  1487.         m = 1;
  1488.       }
  1489.       else
  1490.         m <<= 1;
  1491.     }
  1492.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1493.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1494.   }
  1495.   RETURN(r);
  1496. }
  1497.  
  1498. extern AllocRing _libgxx_fmtq;
  1499.  
  1500. void BitString::printon (ostream& os, char f, char t) const
  1501. {
  1502.   unsigned int  xl = rep->len;
  1503.   const _BS_word* ptr = rep->s;
  1504.   register streambuf *sb = os.rdbuf();
  1505.   _BS_word a = 0;
  1506.  
  1507.   for (unsigned int  i = 0; i < xl; ++i)
  1508.   {
  1509.     if (i % BITSTRBITS == 0)
  1510.       a = *ptr++;
  1511.     sb->sputc((a & 1)? t : f);
  1512.     a >>= 1;
  1513.   }
  1514. }
  1515. const char* BitStringtoa(const BitString& x, char f, char t)
  1516. {
  1517.   int wrksiz = x.length() + 2;
  1518.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  1519.   ostrstream stream(fmtbase, wrksiz);
  1520.   
  1521.   x.printon(stream, f, t);
  1522.   stream << ends;
  1523.   return fmtbase;
  1524. }
  1525.  
  1526. ostream& operator << (ostream& s, const BitString& x)
  1527. {
  1528.   if (s.opfx())
  1529.     x.printon(s);
  1530.   return s;
  1531. }
  1532.  
  1533. const char* BitPatterntoa(const BitPattern& p, char f,char t,char x)
  1534. {
  1535.   unsigned int  pl = p.pattern.rep->len;
  1536.   unsigned int  ml = p.mask.rep->len;
  1537.   unsigned int  l = (pl <= ml)? pl : ml;
  1538.  
  1539.   int wrksiz = l + 2;
  1540.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  1541.   ostrstream stream(fmtbase, wrksiz);
  1542.   
  1543.   p.printon(stream, f, t, x);
  1544.   stream << ends;
  1545.   return fmtbase;
  1546. }
  1547.  
  1548. void BitPattern::printon(ostream& s, char f,char t,char x) const
  1549. {
  1550.   unsigned int  pl = pattern.rep->len;
  1551.   unsigned int  ml = mask.rep->len;
  1552.   unsigned int  l = (pl <= ml)? pl : ml;
  1553.   register streambuf *sb = s.rdbuf();
  1554.  
  1555.   const _BS_word* ps = pattern.rep->s;
  1556.   const _BS_word* ms = mask.rep->s;
  1557.   _BS_word a = 0;
  1558.   _BS_word m = 0;
  1559.  
  1560.   for (unsigned int  i = 0; i < l; ++i)
  1561.   {
  1562.     if (i % BITSTRBITS == 0)
  1563.     {
  1564.       a = *ps++;
  1565.       m = *ms++;
  1566.     }
  1567.     if (m & 1)
  1568.       sb->sputc((a & 1)? t : f);
  1569.     else
  1570.       sb->sputc(x);
  1571.     a >>= 1;
  1572.     m >>= 1;
  1573.   }
  1574. }
  1575.  
  1576. ostream& operator << (ostream& s, const BitPattern& x)
  1577. {
  1578.   if (s.opfx())
  1579.     x.printon(s);
  1580.   return s;
  1581. }
  1582.  
  1583.  
  1584. int BitString::OK() const
  1585. {
  1586.   int v = rep != 0;             // have a rep;
  1587.   v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
  1588.   if (!v) error("invariant failure");
  1589.   return v;
  1590. }
  1591.  
  1592. int BitSubString::OK() const
  1593. {
  1594.   int v = S.OK();               // valid BitString
  1595.   v &= pos + len <= S.rep->len; // within bounds of targ
  1596.   if (!v) S.error("BitSubString invariant failure");
  1597.   return v;
  1598. }
  1599.  
  1600. int BitPattern::OK() const
  1601. {
  1602.   int v = pattern.OK() && mask.OK();
  1603.   if (!v) pattern.error("BitPattern invariant failure");
  1604.   return v;
  1605. }
  1606.  
  1607.